/**
   Copyright 2013 andrew.bossy@gmail.com

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/

package com.andrewbossy.surflex
{
	import mx.collections.ArrayCollection;
	
	/** Sample code:
	 <listing>
	 var sql:Surflex = new Surflex();
	 sql.CreateTable("Product", "ProductId", Product.generateTestData());
	 sql.CreateIndex("Product", "CategoryId");
	 sql.CreateTable("Category", "CategoryId", Category.generateTestData());
	 sql.CreateTable("Order", "OrderId", Order.generateTestData());
	 sql.CreateTable("OrderItem", "OrderItemId", OrderItem.generateTestData());
	 sql.CreateIndex("OrderItem", "ProductId");
	 sql.CreateIndex("OrderItem", "OrderId");
	 
	 sql.Insert("Order", new Order(4, "NO 000459", null));
	 var orderItem:OrderItem = new OrderItem(15, 4, 8, 8, 400);
	 sql.Insert("OrderItem", orderItem);
	 orderItem.Price -= 100;
	 sql.Update("OrderItem", orderItem);
	 sql.Delete("Order", function(order:Order):Boolean{return order.OrderId == 4;});
	 
	 sql.CreateTable("Category2", "CategoryId", Category.generateTestData());
	 
	 var result:Array;
	 result = sql.Select("SELECT Category.Name AS Category, Product.Name AS Product, OrderItem.Quantity AS Quantity"
	 + ", OrderItem.Price AS Price, Category2.* AS Mistake"
	 + " FROM Category"
	 + " INNER JOIN Product ON Category.CategoryId = Product.CategoryId"
	 + " INNER JOIN OrderItem ON Product.ProductId = OrderItem.ProductId"
	 + " INNER JOIN Order ON OrderItem.OrderId = Order.OrderId"
	 + " LEFT JOIN Category2 ON Product.ProductId = Category2.CategoryId"
	 + " WHERE Product, Order"
	 + " ORDER BY Category ASC, Product DESC", new <Function>[
	 function(product:Product):Boolean{return product.Status;},
	 function(order:Order):Boolean{return order.OrderId == 2;}
	 ]); 
	 </listing>*/
	public class Surflex
	{
		private static const INNER_JOIN:int = 1;
		private static const LEFT_JOIN:int = 2;
		
		private static const PRIMARY_KEY:int = 0;
		
		private static const LEFT_SIDE:int = 0;
		private static const RIGHT_SIDE:int = 1;
		
		private static const NULL:int = -1;
		
		private var tables_:Vector.<String>;
		private var clusters_:Vector.<Vector.<Object>>;
		private var indexNames_:Vector.<Vector.<String>>;
		private var indexLeads_:Vector.<Vector.<Vector.<int>>>;
		private var indexDrivens_:Vector.<Vector.<Vector.<int>>>;
		
		public function Surflex()
		{
			tables_ = new Vector.<String>();
			clusters_ = new Vector.<Vector.<Object>>();
			indexNames_ = new Vector.<Vector.<String>>();
			indexLeads_ = new Vector.<Vector.<Vector.<int>>>();
			indexDrivens_ = new Vector.<Vector.<Vector.<int>>>();
		}
		
		/** Creates a new table. Primary Key is a name of property of stored objects that will be used for the first index for the table.
		 * data can be Array or ArrayCollection of initial objects. */
		public function CreateTable(table:String, primaryKey:String, data:Object = null):void
		{
			try
			{
				var cluster:Vector.<Object> = new Vector.<Object>();
				if (data && data is Array)
					cluster = Vector.<Object>((data as Array).concat());
				else if (data && data is ArrayCollection)
					cluster = Vector.<Object>((data as ArrayCollection).source.concat());
				
				cluster.sort(function(x:Object, y:Object):int{if (x[primaryKey] < y[primaryKey]) return -1; else if (x[primaryKey] > y[primaryKey]) return 1; else return 0;});
				tables_.push(table);
				clusters_.push(cluster);
				indexNames_.push(new <String>[primaryKey]);

				var indexLeads:Vector.<int> = new Vector.<int>(cluster.length);
				var indexDrivens:Vector.<int> = new Vector.<int>(cluster.length);
				cluster.forEach(function(e:Object, i:int, a:Vector.<Object>):void
				{
					indexLeads[i] = i;
					indexDrivens[i] = i;
				});
				indexLeads_.push(new <Vector.<int>>[indexLeads]);
				indexDrivens_.push(new <Vector.<int>>[indexDrivens]);
			}
			catch (ex:Error)
			{
				ex.message = "Fatal error in Surflex.CreateTable.\n" + ex.message;
				throw ex;
			}
		}
		
		/** Remove table and all indexes and references to data objects.
		 * Set ifExists to check if table exists before to drop. */
		public function DropTable(table:String, ifExists:Boolean = false):void
		{
			try
			{
				var t:int = tables_.indexOf(table);
				if (t < 0)
				{
					if (ifExists)
						return;
					else
						throw new Error("Unknown table name " + table);
				}
				
				tables_.splice(t, 1);
				clusters_.splice(t, 1);
				indexNames_.splice(t, 1);
				indexLeads_.splice(t, 1);
				indexDrivens_.splice(t, 1);
			}
			catch (ex:Error)
			{
				ex.message = "Fatal error in Surflex.DropTable.\n" + ex.message;
				throw ex;
			}
		}
		
		/** Creates a new index by property name of data objects. Needed for JOIN by foreign keys. */
		public function CreateIndex(table:String, key:String):void
		{
			try
			{
				var t:int = tables_.indexOf(table);
				if (t < 0)
					throw new Error("Unknown table name " + table);
				var cluster:Vector.<Object> = clusters_[t];
				
				var indexLeads:Vector.<int> = new Vector.<int>(cluster.length);
				var indexDrivens:Vector.<int> = new Vector.<int>(cluster.length);
				cluster.forEach(function(e:Object, i:int, a:Vector.<Object>):void
				{
					indexLeads[i] = i;
				});
				indexLeads.sort(function(x:int, y:int):int{if (cluster[x][key] < cluster[y][key]) return -1; else if (cluster[x][key] > cluster[y][key]) return 1; else return 0;});
				indexLeads.forEach(function(e:int, i:int, a:Vector.<int>):void
				{
					indexDrivens[e] = i;
				});

				indexLeads_[t].push(indexLeads);
				indexDrivens_[t].push(indexDrivens);
				indexNames_[t].push(key);
			}
			catch (ex:Error)
			{
				ex.message = "Fatal error in Surflex.CreateIndex.\n" + ex.message;
				throw ex;
			}
		}
		
		/** Inserts a new object into table and updates all relates indexes. */
		public function Insert(table:String, obj:Object):void
		{
			try
			{
				var t:int = tables_.indexOf(table);
				if (t < 0)
					throw new Error("Unknown table name " + table);
				var cluster:Vector.<Object> = clusters_[t];
				
				var p:int, ploc:int, sloc:int;
				
				ploc = locateInSortedVector(obj[indexNames_[t][PRIMARY_KEY]], cluster, indexNames_[t][PRIMARY_KEY]);
				cluster.splice(ploc, 0, obj);
				
				indexNames_[t].forEach(function(e:String, i:int, a:Vector.<String>):void
				{
					indexLeads_[t][i].push(cluster.length - 1);
					indexDrivens_[t][i].push(0);
					indexLeads_[t][i].sort(function(x:int, y:int):int{if (cluster[x][e] < cluster[y][e]) return -1; else if (cluster[x][e] > cluster[y][e]) return 1; else return 0;});
					indexLeads_[t][i].forEach(function(e1:int, i1:int, a1:Vector.<int>):void
					{
						indexDrivens_[t][i][e1] = i1;
					});
				});	
				
			}
			catch (ex:Error)
			{
				ex.message = "Fatal error in Surflex.Insert.\n" + ex.message;
				throw ex;
			}
		}
		
		/** Updates all relates indexes for the data object that was modified outside. */
		public function Update(table:String, obj:Object):void
		{
			try
			{
				var t:int = tables_.indexOf(table);
				if (t < 0)
					throw new Error("Unknown table name " + table);
				var cluster:Vector.<Object> = clusters_[t];
				
				var ploc:int, sloc:int;
				ploc = cluster.indexOf(obj);
				if (ploc < 0)
					throw new Error("Object cannot be found. Primary Key: " + obj[indexNames_[t][0]]);
				
				indexNames_[t].forEach(function(e:String, i:int, a:Vector.<String>):void
				{
					indexLeads_[t][i].sort(function(x:int, y:int):int{if (cluster[x][e] < cluster[y][e]) return -1; else if (cluster[x][e] > cluster[y][e]) return 1; else return 0;});
					indexLeads_[t][i].forEach(function(e1:int, i1:int, a1:Vector.<int>):void
					{
						indexDrivens_[t][i][e1] = i1;
					});
				});	
				
				
			}
			catch (ex:Error)
			{
				ex.message = "Fatal error in Surflex.Update.\n" + ex.message;
				throw ex;
			}
		}
		
		/** Removes the data object from the table and updates indexes. */
		public function Delete(table:String, where:Function):void
		{
			try
			{
				var t:int = tables_.indexOf(table);
				if (t < 0)
					throw new Error("Unknown table name " + table);
				var cluster:Vector.<Object> = clusters_[t];

				var p:int, ploc:int, sloc:int;

				ploc = 0;
				while (ploc < cluster.length)
				{
					if (where(cluster[ploc]))
					{
						cluster.splice(ploc, 1);
						
						indexLeads_[t].forEach(function(e:Vector.<int>, i:int, a:Vector.<Vector.<int>>):void
						{
							for (p = ploc + 1; p < e.length; p++)
								e[indexDrivens_[t][i][p]]--;
							sloc = indexDrivens_[t][i][ploc];
							e.splice(sloc, 1);
							indexDrivens_[t][i].pop();
							e.forEach(function(e1:int, i1:int, a1:Vector.<int>):void
							{
								indexDrivens_[t][i][e1] = i1;
							});
						});
					}
					else
						ploc++;
				}

			}
			catch (ex:Error)
			{
				ex.message = "Fatal error in Surflex.Delete.\n" + ex.message;
				throw ex;
			}
		}
		
		/** Check index for a table for correctness */
		public function CheckIndex(table:String, index:String):void
		{
			try
			{
				var t:int = tables_.indexOf(table);
				if (t < 0)
					throw new Error("Unknown table name " + table);
				var cluster:Vector.<Object> = clusters_[t];
				
				var idx:int = indexNames_[t].indexOf(index);
				if (idx < 0)
					throw new Error("Unknown index name " + index);
				
				var key:String = indexNames_[t][idx];
				
				indexLeads_[t][idx].forEach(function(e:int, i:int, a:Vector.<int>):void
				{
					if (i > 0 && cluster[e][key] < cluster[indexLeads_[t][idx][i - 1]][key])
						throw new Error("Index " + index + " in table " + table + " is broken for values: " + cluster[indexLeads_[t][idx][i - 1]][key] + ", " + cluster[e][key]);
					
					if (indexDrivens_[t][idx][e] != i)
						throw new Error("Index " + index + " in table " + table + " is broken.");
				});
				
			}
			catch (ex:Error)
			{
				ex.message = "Fatal error in Surflex.CheckIndex.\n" + ex.message;
				throw ex;
			}
		}
		
		
		private static const SELECT_IDX:int = 0;
		private static const FROM_IDX:int = 1;
		private static const WHERE_IDX:int = 2;
		private static const GROUP_IDX:int = 3
		private static const ORDER_IDX:int = 4;
		
		private static const DISTINCT_FLAG:int = 0;
		
		private static const NONE_AGGR:int = 0;
		private static const COUNT_AGGR:int = 1;
		private static const SUM_AGGR:int = 2;
		private static const MIN_AGGR:int = 3;
		private static const MAX_AGGR:int = 4;
		private static const AVG_AGGR:int = 5;
		
		/** Performs SELECT from the tables. Sample: 
		 * "SELECT Category.Name AS CategoryName, Product.Name AS ProductName, OrderItem.Quantity AS Quantity, OrderItem.Price AS Price, Resource.URI AS PictureUrl 
		 * FROM Category 
		 * INNER JOIN Product ON Category.CategoryId = Product.CategoryId
		 * INNER JOIN OrderItem ON Product.ProductId = OrderItem.ProductId 
		 * INNER JOIN Order ON OrderItem.OrderId = Order.OrderId
		 * LEFT JOIN Resource ON Product.ResourceId = Resource.ResourceId
		 * WHERE Product, Order
		 * ORDER BY CategoryName ASC, ProductName ASC"
		 * Restrictions: Selected names must have table name and column (object property) name and alias after "AS".
		 * If use * after column name it will place whole data object in the resulting array item.
		 * No calculations allowed in the select part. It is allowed only INNER and LEFT JOIN and only by one key pair with strict =. Format has to be the same table.column.
		 * WHERE clause is optional and lists names of tables that corresponds to the array of filtering function (whereFunctions). Each function receives data object of corresponding type for matching and has to return Boolean.
		 * ORDER BY clause is optional and can list any names that were used in SELECT clause.
		 * GROUP BY can use names from the SELECT clause and following aggregate functions are supported: MIN, MAX, COUNT, SUM, AVG
		 * The result will be an Array of Objects that have properties as column names.
		 * If there is only one selected column, it will be placed directly in the resulting array, without wrapping in generic Object.
		 * SELECT DISTINCT is also available.
		 * */
		public function Select(sql:String, whereFunctions:Vector.<Function>):Array
		{
			var clauses:Vector.<String> = new Vector.<String>(5);
			var flags:Vector.<Object> = new Vector.<Object>(1);
			parseSql(sql, clauses);
			
			var joinTypes:Vector.<int> = new Vector.<int>();
			var leftCols:Vector.<int> = new Vector.<int>();
			var rightCols:Vector.<int> = new Vector.<int>();
			var leftKeys:Vector.<int> = new Vector.<int>();
			var rightKeys:Vector.<int> = new Vector.<int>();
			parseFrom(clauses[FROM_IDX], joinTypes, leftCols, rightCols, leftKeys, rightKeys);
			
			var whereCols:Vector.<int> = new Vector.<int>();
			parseWhere(clauses[WHERE_IDX], whereCols);

			var selectCols:Vector.<int> = new Vector.<int>();
			var selectProperties:Vector.<String> = new Vector.<String>();
			var selectNames:Array = new Array();
			var selectAggregators:Vector.<int> = new Vector.<int>();
			parseSelect(clauses[SELECT_IDX], selectCols, selectProperties, selectNames, selectAggregators, flags);
			
			var groupCols:Vector.<int> = new Vector.<int>();
			var groupNames:Array = new Array();
			parseGroup(clauses[GROUP_IDX], groupCols, groupNames, selectNames, selectAggregators);
			
			var orderCols:Vector.<int> = new Vector.<int>();
			var orderNames:Array = new Array();
			var orderDesc:Vector.<Boolean> = new Vector.<Boolean>();
			parseOrder(clauses[ORDER_IDX], orderCols, orderNames, orderDesc, selectNames);
			
			var joins:Vector.<Vector.<int>>;
			joins = join(joinTypes, leftCols, rightCols, leftKeys, rightKeys, whereCols, whereFunctions);
			
			var selectColsIsNumeric:Vector.<Boolean> = new Vector.<Boolean>(selectCols.length);
			var results:Array;
			results = select(selectCols, rightCols, selectNames, selectProperties, selectColsIsNumeric, joins);

			if (selectAggregators.some(function(e:int, i:int, a:Vector.<int>):Boolean{return e > NONE_AGGR;})
				|| groupCols.length > 0)
					results = group(groupCols, groupNames, selectNames, selectAggregators, selectColsIsNumeric, results);

			if (flags[DISTINCT_FLAG] == true && results.length > 0)
				results = distinct(selectCols, selectNames, selectColsIsNumeric, results);
			
			results = order(orderCols, orderNames, orderDesc, selectColsIsNumeric, results);
			
			var property:String;
			if (selectNames.length == 1)
			{
				property = selectNames[0];
				results = results.map(function(e:Object, i:int, a:Array):Object
				{
					return e[property];
				});
			}
			
			return results;
		}
		
		private function parseSql(sql:String, clauses:Vector.<String>):void
		{
			sql = " " + sql + " ";
			sql = sql.replace(/\s+/gs, " ");
			sql = sql.replace(/\s*,\s*/gs, ", ");
			sql = sql.replace(/\s*\.s*/gs, ".");
			sql = sql.replace(/\s*=\s*/gs, " = ");
			sql = sql.replace(/\s*\(\s*/gs, "(");
			sql = sql.replace(/\s*\)/gs, ")");
			sql = sql.substr(0, sql.length - 1);
			
			var bClause:Vector.<int> = new Vector.<int>(5);
			var eClause:Vector.<int> = new Vector.<int>(5);

			bClause[SELECT_IDX] = sql.indexOf(" SELECT ");
			eClause[SELECT_IDX] = bClause[SELECT_IDX] + " SELECT ".length;
			bClause[FROM_IDX] = sql.indexOf(" FROM ");
			eClause[FROM_IDX] = bClause[FROM_IDX] + " FROM ".length;
			bClause[WHERE_IDX] = sql.indexOf(" WHERE ");
			eClause[WHERE_IDX] = bClause[WHERE_IDX] + " WHERE ".length;
			bClause[GROUP_IDX] = sql.indexOf(" GROUP BY ");
			eClause[GROUP_IDX] = bClause[GROUP_IDX] + " GROUP BY ".length;
			bClause[ORDER_IDX] = sql.indexOf(" ORDER BY ");
			eClause[ORDER_IDX] = bClause[ORDER_IDX] + " ORDER BY ".length;
				
			if (bClause[SELECT_IDX] < 0)
				throw new Error("Missed SELECT clause");
			if (bClause[FROM_IDX] < 0)
				throw new Error("Missed FROM clause");

			var ic:int;
			var i:int;
			for (ic = 0; ic < bClause.length; ic++)
			{
				if (bClause[ic] < 0)
					continue;

				for (i = ic + 1; i < bClause.length; i++)
					if(bClause[i] >= 0)
						break;
				if (i < bClause.length)
					clauses[ic] = sql.slice(eClause[ic], bClause[i]);
				else
					clauses[ic] = sql.slice(eClause[ic]);
			}
		}
		
		private function parseFrom(from:String, joinTypes:Vector.<int>, leftCols:Vector.<int>, rightCols:Vector.<int>, leftKeys:Vector.<int>, rightKeys:Vector.<int>):void
		{
			
			var betweenJoin:Array = from.split(" JOIN ");
			var colQty:int = betweenJoin.length;
			
			joinTypes.length = colQty;
			leftCols.length = colQty;
			rightCols.length = colQty;
			leftKeys.length = colQty;
			rightKeys.length = colQty;
			
			leftCols[0] = tables_.indexOf(betweenJoin[0].split(" ")[0]);
			if (leftCols[0] < 0)
				throw new Error("Unknown table name in FROM " + betweenJoin[0].split(" ")[0]);
			rightCols[0] = leftCols[0];
			leftKeys[0] = PRIMARY_KEY;
			rightKeys[0] = PRIMARY_KEY;
			
			if (colQty < 2)
				return;
			
			var j:int;
			var i:int;
			for (j = 0; j < colQty - 1; j++)
			{
				i = betweenJoin[j].lastIndexOf(" INNER");
				if (i >= 0)
					joinTypes[j + 1] = INNER_JOIN;
				else
				{
					i = betweenJoin[j].lastIndexOf(" LEFT");
					if (i >= 0)
						joinTypes[j + 1] = LEFT_JOIN;
					else
						throw new Error("JOIN has to be either INNER or LEFT.");
				}
				betweenJoin[j] = betweenJoin[j].substring(0, i);
			}
			
			var betweenEqual:Array;
			var betweenDot:Array;
			var key:String;
			var c:int;
			
			for (j = 1; j < colQty; j++)
			{
				betweenEqual = betweenJoin[j].split(" ON ", 2)[RIGHT_SIDE].split(" = ", 2);
				
				betweenDot = betweenEqual[LEFT_SIDE].split(".", 2);
				c = tables_.indexOf(betweenDot[LEFT_SIDE]);
				if (c < 0)
					throw new Error("Unknown table name in FROM " + betweenDot[LEFT_SIDE]);
				leftCols[j] = c;
				leftKeys[j] = indexNames_[c].indexOf(betweenDot[RIGHT_SIDE]);
				if (leftKeys[j] < 0)
					throw new Error("Unknown index name in FROM " + betweenDot[RIGHT_SIDE]);
				
				betweenDot = betweenEqual[RIGHT_SIDE].split(".", 2);
				c = tables_.indexOf(betweenDot[LEFT_SIDE]);
				if (c < 0)
					throw new Error("Unknown table name in FROM " + betweenDot[LEFT_SIDE]);		
				rightCols[j] = c;
				rightKeys[j] = indexNames_[c].indexOf(betweenDot[RIGHT_SIDE]);
				if (rightKeys[j] < 0)
					throw new Error("Unknown index name in FROM " + betweenDot[RIGHT_SIDE]);	
			}
			
		}

		
		private function parseWhere(where:String, whereCols:Vector.<int>):void
		{
			if (!where)
				return;
			
			var t:int;
			where.split(", ").forEach(function(e:String, i:int, a:Array):void
			{
				t = tables_.indexOf(e);
				if (t < 0)
					throw new Error("Unknown table name in WHERE " + e);					
				whereCols.push(t);
			});
		}	
		
		private function parseSelect(select:String, selectCols:Vector.<int>, selectProperties:Vector.<String>, selectNames:Array, selectAggregates:Vector.<int>, flags:Vector.<Object>):void
		{
			flags[DISTINCT_FLAG] = false;
			if (select.indexOf("DISTINCT ") == 0)
			{
				flags[DISTINCT_FLAG] = true;
				select = select.substring("DISTINCT ".length);
			}
			
			var betweenAs:Array;
			var betweenDot:Array;
			var t:int;
			var str:String;
			var loc:int;
			select.split(", ").forEach(function(e:String, i:int, a:Array):void
			{
				betweenAs = e.split(" AS ");
				str = betweenAs[LEFT_SIDE];
				loc = str.indexOf("(");
				if (loc >= 0)
				{
					if (str.indexOf("COUNT(") == 0)
						selectAggregates.push(COUNT_AGGR);
					else if (str.indexOf("SUM(") == 0)
						selectAggregates.push(SUM_AGGR);
					else if (str.indexOf("MIN(") == 0)
						selectAggregates.push(MIN_AGGR);
					else if (str.indexOf("MAX(") == 0)
						selectAggregates.push(MAX_AGGR);
					else if (str.indexOf("AVG(") == 0)
						selectAggregates.push(AVG_AGGR);
					else
						throw new Error("Unknown aggregate function in SELECT " + str);
						
					str = str.slice(loc + 1, str.length - 1);
				}
				else
					selectAggregates.push(NONE_AGGR);
				betweenDot = str.split(".");
				t = tables_.indexOf(betweenDot[LEFT_SIDE]);
				if (t < 0)
					throw new Error("Unknown table name in SELECT " + betweenDot[LEFT_SIDE]);					
				selectCols.push(t);
				selectProperties.push(betweenDot[RIGHT_SIDE]);
				selectNames.push(betweenAs[RIGHT_SIDE]);
			});
		}

		private function parseGroup(group:String, groupCols:Vector.<int>, groupNames:Array, selectNames:Array, selectAggregators:Vector.<int>):void
		{
			if (!group)
				return;
			
			var t:int;
			group.split(", ").forEach(function(e:String, i:int, a:Array):void
			{
				groupNames.push(e);
				t = selectNames.indexOf(e);
				if (t < 0)
					throw new Error("Unknown SELECT column name in GROUP BY " + e);
				groupCols.push(t);
			});
			return;
		}
		
		private function parseOrder(order:String, orderCols:Vector.<int>, orderNames:Array, orderDesc:Vector.<Boolean>, selectNames:Array):void
		{
			if (!order)
				return;
			var t:int;
			
			var betweenSpace:Array;
			order.split(", ").forEach(function(e:String, i:int, a:Array):void
			{
				betweenSpace = e.split(" ");
				orderNames.push(betweenSpace[LEFT_SIDE]);
				t = selectNames.indexOf(betweenSpace[LEFT_SIDE]);
				if (t < 0)
					throw new Error("Unknown SELECT column name in ORDER BY " + betweenSpace[LEFT_SIDE]);
				orderCols.push(t);
				orderDesc.push(betweenSpace[RIGHT_SIDE] == "DESC");
			});
		}
		
		private function join(joinTypes:Vector.<int>, leftCols:Vector.<int>, rightCols:Vector.<int>, leftKeys:Vector.<int>, rightKeys:Vector.<int>
			, whereCols:Vector.<int>, whereFunctions:Vector.<Function>):Vector.<Vector.<int>>
		{
			var j:int, jl:int, jr:int, tl:int, tr:int, kl:int, kr:int, w:int, il:int, ir:int, value1:int, value2:int;
			var colQty:int = joinTypes.length;
			var joinLeads:Vector.<Vector.<int>> = new Vector.<Vector.<int>>(colQty);
			var joinLeadsIndexDrivens:Vector.<Vector.<int>> = new Vector.<Vector.<int>>(colQty);
			var joinDrivens:Vector.<Vector.<Vector.<int>>> = new Vector.<Vector.<Vector.<int>>>(colQty);

			jr = 0;
			jl = 0;

			tl = leftCols[jr];
			tr = rightCols[jr];
			kl = leftKeys[jr];
			kr = rightKeys[jr];

			joinLeads[jr] = new Vector.<int>();
			joinLeadsIndexDrivens[jr] = new Vector.<int>();
			joinDrivens[jr] = new Vector.<Vector.<int>>(indexLeads_[tr][kr].length);
			w = whereCols.indexOf(tr);
			indexLeads_[tr][kr].forEach(function(e:int, i:int, a:Vector.<int>):void
			{
				if (w < 0 || whereFunctions[w](clusters_[tr][e]))
				{
					ir = joinLeads[jr].push(e) - 1;
					joinLeadsIndexDrivens[jr].push(0);
					joinDrivens[jr][e] = new <int>[ir];
				}
			});
			
			if (colQty < 2)
				return joinLeads;
		
			
			var ilEqual:int, irEqual:int, ilFirstEqual:int, irFirstEqual:int;
			var keyl:*;
			var keyr:*;
			
			var colItem:Object;
			var rightEOF:Boolean;
			
			var lkeyName:String;
			var rkeyName:String;
			var njoinLeads:Vector.<Vector.<int>>;
			var njoinLeadsIndexDrivens:Vector.<Vector.<int>>;
			var njoinDrivens:Vector.<Vector.<Vector.<int>>>;			

			for (jr = 1; jr < colQty; jr++)
			{
			
				tl = leftCols[jr];
				tr = rightCols[jr];
				kl = leftKeys[jr];
				kr = rightKeys[jr];
				
				lkeyName = indexNames_[tl][kl];
				rkeyName = indexNames_[tr][kr];
				
				jl = rightCols.indexOf(tl);

				joinLeads[jr] = new Vector.<int>();
				joinLeadsIndexDrivens[jr] = new Vector.<int>();
				joinDrivens[jr] = new Vector.<Vector.<int>>(clusters_[tr].length);
				w = whereCols.indexOf(tr);
				indexLeads_[tr][kr].forEach(function(e:int, i:int, a:Vector.<int>):void
				{
					if (w < 0 || whereFunctions[w](clusters_[tr][e]))
					{
						ir = joinLeads[jr].push(e) - 1;
						joinLeadsIndexDrivens[jr].push(0);
						joinDrivens[jr][e] = new <int>[ir];
					}
				});
				
				il = 0;
				indexLeads_[tl][kl].forEach(function(e:int, i:int, a:Vector.<int>):void
				{
					if (joinDrivens[jl][e])
					{
						joinDrivens[jl][e].forEach(function(e1:int, i1:int, a1:Vector.<int>):void
						{
							for (j = 0; j < jr; j++)
							{
								value1 = joinLeads[j][il];
								value2 = joinLeads[j][e1];
								if (value1 != NULL)
									joinDrivens[j][value1][joinLeadsIndexDrivens[j][il]] = e1;
								if (value2 != NULL)
									joinDrivens[j][value2][joinLeadsIndexDrivens[j][e1]] = il;

								joinLeads[j][il] = value2;
								joinLeads[j][e1] = value1;
								
								value1 = joinLeadsIndexDrivens[j][il];
								value2 = joinLeadsIndexDrivens[j][e1];
								joinLeadsIndexDrivens[j][il] = value2;
								joinLeadsIndexDrivens[j][e1] = value1;
							}
							il++;
						});
					}
				});
				
				njoinLeads = new Vector.<Vector.<int>>(colQty);
				njoinLeadsIndexDrivens = new Vector.<Vector.<int>>(colQty);
				njoinDrivens = new Vector.<Vector.<Vector.<int>>>(colQty);
				
				for (j = 0; j <= jr; j++)
				{
					njoinLeads[j] = new Vector.<int>();
					njoinLeadsIndexDrivens[j] = new Vector.<int>();
					njoinDrivens[j] = new Vector.<Vector.<int>>(clusters_[rightCols[j]].length);
				}

				il = 0;
				ir = 0;
				while (il < joinLeads[jl].length && (ir < joinLeads[jr].length || joinTypes[jr] == LEFT_JOIN))
				{
					if (joinLeads[jl][il] == NULL) // if we already have a record with left joined nullable left part
					{
						if (joinTypes[jr] == LEFT_JOIN) // so in case of left join we just clone object with null from right
							weld(il, NULL, jr, joinLeads, joinLeadsIndexDrivens, joinDrivens, njoinLeads, njoinLeadsIndexDrivens, njoinDrivens);
						il++;
						continue;
					}
					keyl = clusters_[tl][joinLeads[jl][il]][lkeyName];
					
					if (joinTypes[jr] == LEFT_JOIN && ir >= joinLeads[jr].length) // right part already out of scope, so it is null, applicable only for LEFT JOIN
					{
						// we just clone object with null from right
						weld(il, NULL, jr, joinLeads, joinLeadsIndexDrivens, joinDrivens, njoinLeads, njoinLeadsIndexDrivens, njoinDrivens);
						il++;
						continue;
					}
					
					keyr = clusters_[tr][joinLeads[jr][ir]][rkeyName]; 
					
					if (keyl < keyr)
					{
						if (joinTypes[jr] == LEFT_JOIN)
							weld(il, NULL, jr, joinLeads, joinLeadsIndexDrivens, joinDrivens, njoinLeads, njoinLeadsIndexDrivens, njoinDrivens);
						il++;
					}
					else if (keyl > keyr)
						ir++;
					else // keyl == keyr
					{
						ilFirstEqual = il;
						while (il < joinLeads[jl].length && joinLeads[jl][il] != NULL && clusters_[tl][joinLeads[jl][il]][lkeyName] == keyl)
							il++;
						
						irFirstEqual = ir;
						while (ir < joinLeads[jr].length && joinLeads[jr][ir] != NULL && clusters_[tr][joinLeads[jr][ir]][rkeyName] == keyr)
							ir++;
						
						for (ilEqual = ilFirstEqual; ilEqual < il; ilEqual++)
							for (irEqual = irFirstEqual; irEqual < ir; irEqual++)
								weld(ilEqual, irEqual, jr, joinLeads, joinLeadsIndexDrivens, joinDrivens, njoinLeads, njoinLeadsIndexDrivens, njoinDrivens);
					}
				}
				
				joinLeads = njoinLeads;
				joinLeadsIndexDrivens = njoinLeadsIndexDrivens;
				joinDrivens = njoinDrivens;
				
			}

			return joinLeads;
		}
		
		private function joinCheck(joinLeads:Vector.<Vector.<int>>, joinLeadsIndexDrivens:Vector.<Vector.<int>>, joinDrivens:Vector.<Vector.<Vector.<int>>>):void
		{
			for (var j:int = 0; j < joinLeads.length; j++)
			{
				if (joinLeads[j] == null)
					continue;
				
				joinLeads[j].forEach(function(e:int, i:int, a:Vector.<int>):void
				{
					if(e != NULL)
					{
						if (joinDrivens[j][e][joinLeadsIndexDrivens[j][i]] != i)
							throw new Error("Broken join structure");
					}
				});
				
				joinDrivens[j].forEach(function(e:Vector.<int>, i:int, a:Vector.<Vector.<int>>):void
				{
					if(e != null)
					{
						e.forEach(function(e1:int, i1:int, a1:Vector.<int>):void
						{
							if (joinLeads[j][e1] != i || joinLeadsIndexDrivens[j][e1] != i1)
								throw new Error("Broken join structure");
						});
					}
				});
			}
		}
		
		private function weld(il:int, ir:int, jr:int,
			joinLeads:Vector.<Vector.<int>>,
			joinLeadsIndexDrivens:Vector.<Vector.<int>>,
			joinDrivens:Vector.<Vector.<Vector.<int>>>,
			njoinLeads:Vector.<Vector.<int>>,
			njoinLeadsIndexDrivens:Vector.<Vector.<int>>,
			njoinDrivens:Vector.<Vector.<Vector.<int>>>):void
		{
			var j:int;
			var p:int;
			var pidx:int;
			
			for (j = 0; j < jr; j++)
			{
				pidx = joinLeads[j][il];
				p = njoinLeads[j].push(pidx) - 1;
				
				if (pidx != NULL)
				{
					if(!njoinDrivens[j][pidx])
						njoinDrivens[j][pidx] = new Vector.<int>();
					p = njoinDrivens[j][pidx].push(p) - 1;
					njoinLeadsIndexDrivens[j].push(p);
				}
				else
					njoinLeadsIndexDrivens[j].push(NULL);
			}
			if (ir != NULL)
			{
				pidx = joinLeads[jr][ir];
				p = njoinLeads[jr].push(pidx) - 1;
				if(!njoinDrivens[jr][pidx])
					njoinDrivens[jr][pidx] = new Vector.<int>();
				p = njoinDrivens[jr][pidx].push(p) - 1;
				njoinLeadsIndexDrivens[jr].push(p);
			}
			else
			{
				njoinLeads[jr].push(NULL);
				njoinLeadsIndexDrivens[jr].push(0);
			}

		}

		public function select(selectCols:Vector.<int>, rightCols:Vector.<int>, selectNames:Array, selectProperties:Vector.<String>, selectColsIsNumeric:Vector.<Boolean>, joins:Vector.<Vector.<int>>):Array
		{
			var results:Array = new Array(joins[0].length);
			joins[0].forEach(function(e:int, i:int, a:Vector.<int>):void
			{
				results[i] = new Object();
			});
			
			var value:*;
			selectCols.forEach(function(e:int, i:int, a:Vector.<int>):void
			{
				joins[rightCols.indexOf(e)].forEach(function(e1:int, i1:int, a1:Vector.<int>):void
				{
					if (e1 == NULL)
						results[i1][selectNames[i]] = null;
					else
					{
						if (selectProperties[i] == "*")
							results[i1][selectNames[i]] = clusters_[e][e1];
						else
						{
							value = clusters_[e][e1][selectProperties[i]];
							results[i1][selectNames[i]] = value;
							selectColsIsNumeric[i] = value is int || value is Number || value is Date;
						}
					}
					
				});
			});
			return results;
		}
		
		public function group(groupCols:Vector.<int>, groupNames:Array, selectNames:Array, selectAggregators:Vector.<int>, selectColsIsNumeric:Vector.<Boolean>, array:Array):Array
		{
			var ires:int = 0;
			var results:Array = new Array();		
			if (array.length <= 0)
			{
				if (groupNames.length > 0)
					return results;
				
				results.push(new Object());
				selectNames.forEach(function(e:String, i:int, a:Array):void
				{
					if (selectAggregators[i] == COUNT_AGGR || selectAggregators[i] == SUM_AGGR && selectColsIsNumeric[i])
						results[ires][e] = 0;
					else
						results[ires][e] = null;
				});
				return results;
			}	
			
			var sortOptions:Array;
			if (groupCols.length)
			{
				sortOptions = new Array(groupNames.length);
				groupCols.forEach(function(e:int, i:int, a:Vector.<int>):void
				{
					sortOptions[i] = selectColsIsNumeric[e] ? Array.NUMERIC : 0;
				});
				array.sortOn(groupNames, sortOptions);
			}

			var count:int = 0;
			results.push(new Object());
			var aggValue:*;
			var selValue:*;
			var firstTime:Boolean = true;
			array.forEach(function(e:Object, i:int, a:Array):void
			{
				if (!firstTime && groupNames.some(function(e1:String, i1:int, a1:Array):Boolean{return results[ires][e1] != e[e1];}))
				{
					groupClose(selectNames, selectAggregators, selectColsIsNumeric, count, results);
					results.push(new Object());
					ires ++;
					count = 0;
				}
				
				firstTime = false;
				count++;
					
				selectNames.forEach(function(e1:String, i1:int, a1:Array):void
				{
					aggValue = results[ires][e1];
					selValue = e[e1];
					switch (selectAggregators[i1])
					{
						case COUNT_AGGR:
							aggValue = count;
							break;
						case SUM_AGGR:
						case AVG_AGGR:
							if (aggValue)
								aggValue += selValue;
							else
								aggValue = selValue;
							break;
						case MIN_AGGR:
							if (aggValue)
								aggValue = selValue < aggValue ? selValue : aggValue;
							else
								aggValue = selValue;
							break;
						case MAX_AGGR:
							if (aggValue)
								aggValue = selValue > aggValue ? selValue : aggValue;
							else
								aggValue = selValue;
							break;
						case NONE_AGGR:
							aggValue = selValue;
						default:
					}
					results[ires][e1] = aggValue;
				});

			});
			groupClose(selectNames, selectAggregators, selectColsIsNumeric, count, results);
			return results;
		}

		private function groupClose(selectNames:Array, selectAggregators:Vector.<int>, selectColsIsNumeric:Vector.<Boolean>, count:int, results:Array):void
		{
			var ires:int = results.length - 1;
			selectNames.forEach(function(e:String, i:int, a:Array):void
			{
				if (selectAggregators[i] == AVG_AGGR)
				{
					if (results[ires][e] && selectColsIsNumeric[i] && count > 0)
						results[ires][e] /= count;
					else
						results[ires][e] = null;
				}
			});
		}
		
		private function distinct(selectCols:Vector.<int>, selectNames:Array, selectColsIsNumeric:Vector.<Boolean>, array:Array):Array
		{
			var sortOptions:Array = new Array(selectNames.length);
			selectCols.forEach(function(e:int, i:int, a:Vector.<int>):void
			{
				sortOptions[i] = selectColsIsNumeric[i] ? Array.NUMERIC : 0;
			});
			array.sortOn(selectNames, sortOptions);
		
			var results:Array = new Array();
			var ires:int = results.length - 1;
			var firstTime:Boolean = true;
			array.forEach(function(e:Object, i:int, a:Array):void
			{
				if (firstTime || selectNames.some(function(e1:String, i1:int, a1:Array):Boolean{return results[ires][e1] != e[e1];}))
				{
					firstTime = false;
					results.push(e);
					ires++;
				}
			});
			return results;
		}
		
		private function order(orderCols:Vector.<int>, orderNames:Array, orderDesc:Vector.<Boolean>, selectColsIsNumeric:Vector.<Boolean>, array:Array):Array
		{
			var sortOptions:Array;
			sortOptions = new Array(orderNames.length);
			orderCols.forEach(function(e:int, i:int, a:Vector.<int>):void
			{
				sortOptions[i] = (orderDesc[i] ? Array.DESCENDING : 0) | (selectColsIsNumeric[e] ? Array.NUMERIC : 0);
			});
		
			array.sortOn(orderNames, sortOptions);
			return array;
		}
		
		private static function locateInSortedVector(value:*, vector:Vector.<Object>, property:String):int
		{
			var length:int = vector.length;
			if (length <= 0)
				return 0;

			var min:int = 0;
			var max:int = length - 1;
			var mid:int;
			
			var minVal:* = vector[min][property];
			var maxVal:* = vector[max][property];
			var midVal:*;
			
			if (value <= minVal)
				return 0;
			
			if (value >= maxVal)
				return length;
			
			while (max - min > 1)
			{
				mid = (min + max) / 2;
				midVal = vector[mid][property];
				if (value > midVal)
				{
					min = mid;
					minVal = midVal;
				}
				else if (value < midVal)
				{
					max = mid;
					maxVal = midVal;
				}
				else // value == midVal
					return mid;				
			}
			
			return max;
		}
	
	}
}



